/*
 *多项式相加的练习
 *2018.11.09
 */
#include <stdio.h>
#include <stdlib.h>
typedef struct poly_node *poly_nomial;

struct poly_node {
	int cofe;	//系数
	int expon;	//指数
	struct poly_node * link;
};

poly_nomial read_poly();
void attach(int c, int e, poly_nomial *p_rear);
poly_nomial poly_add(poly_nomial p1, poly_nomial p2);
int compare(const int a , const int b);

int compare(const int a, const int b) {
	return  a - b;
}

poly_nomial read_poly() {
 	poly_nomial p, rear, t;
	int c, e, n;

	scanf ("%d",&n);
	p = (poly_nomial)malloc(sizeof(struct poly_node));
	p->link = NULL;
	rear = p;
	printf("n=%d",n);
	while (n--) {
		scanf ("%d%d",&c,&e);
		attach(c,e,&rear); 	
	}
	t = p;		/*p指向空节点*/
	p = p->link;	/*由p取代空节点指向的第一个数据节点*/
	free(t);	/*清除空节点*/
	return p;	/*返回一个指向不带头结点的单向链表的指针*/
}

void attach(int c, int e, poly_nomial *p_rear) {
	poly_nomial p;
	
	p = (poly_nomial)malloc(sizeof(struct poly_node));
	p->cofe = c;
	p->expon = e;
	p->link = NULL;
	(*p_rear)->link = p;
	*p_rear = p;
}

poly_nomial poly_add(poly_nomial p1, poly_nomial p2) {
	poly_nomial front, rear, temp;
	int sum;
	rear = (poly_nomial)malloc(sizeof(struct poly_node));
	front = rear;
	while (p1 && p2)
		switch (compare(p1->expon, p2->expon)) {
		case 1:
			attach(p1->expon, p1->expon, &rear);
			p1 = p1->link;
			break;
		case -1:
			attach(p2->expon, p2->expon, &rear);
			p2 = p2->link;
			break;
		case 0:
			sum = p1->cofe + p2->cofe;
			if(sum) attach(sum, p1->expon, &rear);
			p1 = p1->link;
			p2 = p2->link;
			break;
	}
	
	for (;p1;p1 = p1->link) attach(p1->cofe, p2->expon, &rear);
	for (;p2;p2 = p2->link) attach(p2->cofe, p2->expon, &rear);
	rear->link = NULL;
	temp = front;
	front = front->link;
	free(temp);
	return front;
}

int main() {
	poly_nomial p1, p2, p_out;
	printf("请输入第一个多项式\n（3x^4 - 5x^2 + 6x^ - 2,"
		" 输入：4 3 4 -5 2 6 1 -2 0）:");
	p1 = read_poly();
        printf("请输入第二个多项式\n（3x^4 - 5x^2 + 6x^ - 2,"
		" 输入：4 3 4 -5 2 6 1 -2 0）:");
	p2 = read_poly();
	p_out = poly_add(p1, p2);
	printf("多项式相加结果：");
	for (;p_out;p_out = p_out->link) {
		printf("%d %d  ",p_out->cofe,p_out->expon);
	}
	
	return 0;
}
